The present invention relates to a transfer device that searches for a header of communication data such as frames and packets and determines the transfer destination.
Conventionally, improvement in transfer performance is always being sought for transfer devices such as routers and switches. Thus, transfer devices need to determine the transfer destination of communication headers using hardware where the processing content cannot be modified such as an LSI, which has a high processing performance, instead of software processing or reconfigurable hardware such as FPGAs.
In search processes by hardware such as LSI, the format of the header to be handled is determined in advance, and the hardware uses a predetermined field as a search key and performs a search according to a predetermined search mode.
When determining the next transfer destination from the destination IP address, for example, the transfer device performs a search by a predetermined search mode referred to as longest prefix search to determine the next transfer destination. In a search process by hardware such as an LSI, there was a problem that there was no backwards compatibility for searching frames of new header formats that appeared after the LSI was commercialized.
In order to solve this problem, the communication device of WO/2014/125636 has a packet processing-only hardware that performs packet search and a transfer process, and a packet analysis processor that can programmably analyze the packet format and perform a packet transfer process. When determining whether the packet format can be processed by the packet processing-only hardware, if it is determined that the packet format cannot be processed by the packet processing-only hardware, the packet analysis process converts the packet to a processable packet format and transfers the packet to the packet processing-only hardware.
If the packet header process cannot be performed by the packet processing-only hardware, then the communication device of WO/2014/125636 converts the packet to a processable packet format. However, it is not possible to flexibly perform a search according to search specifications required for newly emerged frame header formats in a latter stage packet processing-only hardware, through packet conversion alone.
One example is a case in which the transfer destination is determined with a long field of approximately 32 bits as the search key. In such a case, the length of the field to be the search key does not change by simply converting the packet header. Thus, the packet processing-only hardware needs to search the destination with the 32 bit search key. When searching for the 32 bit field, if simply pulling a table with the 32-bit value as an index, a table with 4 giga-entries (232) needs to be looked up, which requires a large amount of memory. Similarly, if the search field width is 48 bits, for example, then a table with 256 tera-entries (248) needs to be looked up, which requires a nearly impossible amount of memory.